前言

昨天大致介紹圖形的定義，今天就來介紹幾個圖形的資料結構!

圖(Graph)，是一種用來描述點與點之間關係的資料結構，也可以說是記錄關聯性的結構

圖形的表示法

圖形的資料結構非常多，書中介紹了常用的兩種: 鄰接矩陣 Adjacency matrix 和 鄰接串列 Adjacency list

• 鄰接矩陣 Adjacency matrix
  • 含有n個頂點的圖形，其Adjacency matrix的大小就會是 n列 x n行。
  • matrix中的元素只會是0或1
  1. 以下圖(無向圖)作為例子 =>
     
     -> Adjacency matrix =
     
     • 從矩陣的1，可以看出兩個頂點是有連線的。
     • 因為頂點不可能自成迴路，所以主對角線上的元素都會是0。
     • 無向圖的Adjacency matrix一定會是對稱矩陣。
     • 將每一列的數值相加就是該頂點的分支度。
       例如 : 第0列數值相加為 0+1+1+1 = 3，所以A點分支度為3。
  2. 以下圖(有向圖)作為例子 =>
     
     -> Adjacency matrix =
     
     • 矩陣中，第0列有1個非零數，表示A點出分支度為1。
     • 矩陣中，第0行有2個非零數，表示A點入分支度為2。
     • 有向圖的Adjacency matrix不一定為對稱矩陣。
• 鄰接串列 Adjacency list
  • 利用串列的方式將相鄰的頂點串起來。
  • 可以節省記憶體空間。
  • 同樣以下圖(無向圖)為例
    
  • Adjacency list ->
    
  • 同樣以下圖(有向圖)為例
    
  • Adjacency list ->
  • 

參考

細談資料結構 第六版
ISBN 978-986-312-014-8